/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package org.fjala.softure.tree;

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;

/**
 * Base implementation of a tree to help the development. 
 * This implementations uses the iterator to perform the most of its methods. 
 * So, it's recomendable to implement the iterator.
 * 
 * @author Dann Meneses
 */
public abstract class AbstractTree<E> implements Tree<E> {

    protected Node<E> root;

    public AbstractTree(Node<E> root) {
        this.root = root;
    }

    public AbstractTree() {
    }
    
    @Override
    public Node<E> getRoot() {
        return root;
    }

    @Override
    public boolean isEmpty() {
        if (root == null) {
            return true;
        }

        return false;
    }

    @Override
    public boolean remove(Object o) {
        Iterator<E> iterator = iterator();
        if (o == null) {
            while (iterator.hasNext()) {
                if (iterator.next() == null) {
                    iterator.remove();
                    return true;
                }
            }
        } else {
            while (iterator.hasNext()) {
                if (o.equals(iterator.next())) {
                    iterator.remove();
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public boolean contains(Object o) {
        Iterator<E> iterator = iterator();
        if (o == null) {
            while (iterator.hasNext()) {
                if (iterator.next() == null) {
                    return true;
                }
            }
        } else {
            while (iterator.hasNext()) {
                if (o.equals(iterator.next())) {
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public Object[] toArray() {
        Object[] res = new Object[size()];
        Iterator<E> iterator = iterator();
        for (int i = 0; i < res.length; i++) {
            if (!iterator.hasNext()) 
            {
                return Arrays.copyOf(res, i);
            }
            res[i] = iterator.next();
        }
        return iterator.hasNext() ? finishToArray(res, iterator) : res;
    }

    @Override
    public <T> T[] toArray(T[] a) {
        int size = size();
        T[] res = a.length >= size ? a
                : (T[]) java.lang.reflect.Array
                .newInstance(a.getClass().getComponentType(), size);
        Iterator<E> iterator = iterator();

        for (int i = 0; i < res.length; i++) {
            if (!iterator.hasNext()) { 
                if (a != res) {
                    return Arrays.copyOf(res, i);
                }
                res[i] = null; 
                return res;
            }
            res[i] = (T) iterator.next();
        }
        return iterator.hasNext() ? finishToArray(res, iterator) : res;
    }

    private static <T> T[] finishToArray(T[] array, Iterator<?> iterator) {
        int i = array.length;
        while (iterator.hasNext()) {
            int cap = array.length;
            if (i == cap) {
                int newCap = ((cap / 2) + 1) * 3;
                if (newCap <= cap) { 
                    if (cap == Integer.MAX_VALUE) {
                        throw new OutOfMemoryError("Required array size too large");
                    }
                    newCap = Integer.MAX_VALUE;
                }
                array = Arrays.copyOf(array, newCap);
            }
            array[i++] = (T) iterator.next();
        }
        
        return (i == array.length) ? array : Arrays.copyOf(array, i);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        Iterator<?> iterator = c.iterator();
        while (iterator.hasNext()) {
            if (!contains(iterator.next())) {
                return false;
            }
        }
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        Iterator<? extends E> iterator = c.iterator();
        while (iterator.hasNext()) {
            if (add(iterator.next())) {
                modified = true;
            }
        }
        return modified;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        boolean modified = false;
        Iterator<?> iterator = iterator();
        while (iterator.hasNext()) {
            if (c.contains(iterator.next())) {
                iterator.remove();
                modified = true;
            }
        }
        return modified;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        boolean modified = false;
        Iterator<E> iterator = iterator();
        while (iterator.hasNext()) {
            if (!c.contains(iterator.next())) {
                iterator.remove();
                modified = true;
            }
        }
        return modified;
    }

    @Override
    public void clear() {
        root = null;
    }

    @Override
    public String toString() {
        return root.toString();
    }
}
